// Range v3 library
//
//  Copyright Eric Niebler 2014
//
//  Use, modification and distribution is subject to the
//  Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)
//
// Project home: https://github.com/ericniebler/range-v3
//
//  Copyright 2005 - 2007 Adobe Systems Incorporated
//  Distributed under the MIT License(see accompanying file LICENSE_1_0_0.txt
//  or a copy at http://stlab.adobe.com/licenses.html)

//===----------------------------------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include <nanorange/algorithm/pop_heap.hpp>
#include <memory>
#include <random>
#include <algorithm>
#include <functional>
#include "../catch.hpp"
#include "../test_utils.hpp"
#include "../test_iterators.hpp"

namespace stl2 = nano;

namespace {

std::mt19937 gen;

void test_1(int N)
{
	int* ia = new int[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N);
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(ia, ia + i) == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1));
	}
	CHECK(stl2::pop_heap(ia, ia) == ia);
	delete[] ia;
}

void test_2(int N)
{
	int* ia = new int[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N);
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(ia, sentinel<int*>(ia + i)) == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1));
	}
	CHECK(stl2::pop_heap(ia, ia) == ia);
	delete[] ia;
}

void test_3(int N)
{
	int* ia = new int[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N);
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(::as_lvalue(stl2::subrange(ia, ia + i)))
					  == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1));
	}
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N);
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(stl2::subrange(ia, ia + i))
					  == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1));
	}
	CHECK(stl2::pop_heap(ia, ia) == ia);
	delete[] ia;
}

void test_4(int N)
{
	int* ia = new int[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N);
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(
				::as_lvalue(stl2::subrange(ia, sentinel<int*>(ia + i))))
					  == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1));
	}
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N);
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(
				stl2::subrange(ia, sentinel<int*>(ia + i)))
					  == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1));
	}
	CHECK(stl2::pop_heap(ia, ia) == ia);
	delete[] ia;
}

void test_5(int N)
{
	int* ia = new int[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N, std::greater<int>());
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(ia, ia + i, std::greater<int>()) == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1, std::greater<int>()));
	}
	CHECK(stl2::pop_heap(ia, ia, std::greater<int>()) == ia);
	delete[] ia;
}

void test_6(int N)
{
	int* ia = new int[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N, std::greater<int>());
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(ia, sentinel<int*>(ia + i), std::greater<int>())
					  == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1, std::greater<int>()));
	}
	CHECK(stl2::pop_heap(ia, sentinel<int*>(ia), std::greater<int>()) == ia);
	delete[] ia;
}

void test_7(int N)
{
	int* ia = new int[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N, std::greater<int>());
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(::as_lvalue(stl2::subrange(ia, ia + i)),
							 std::greater<int>()) == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1, std::greater<int>()));
	}
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N, std::greater<int>());
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(stl2::subrange(ia, ia + i),
							 std::greater<int>()) == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1, std::greater<int>()));
	}
	CHECK(stl2::pop_heap(ia, ia, std::greater<int>()) == ia);
	delete[] ia;
}

void test_8(int N)
{
	int* ia = new int[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N, std::greater<int>());
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(
				::as_lvalue(stl2::subrange(ia, sentinel<int*>(ia + i))),
				std::greater<int>()) == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1, std::greater<int>()));
	}
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N, std::greater<int>());
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(stl2::subrange(ia, sentinel<int*>(ia + i)),
							 std::greater<int>()) == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1, std::greater<int>()));
	}
	CHECK(stl2::pop_heap(ia, sentinel<int*>(ia), std::greater<int>()) == ia);
	delete[] ia;
}

struct indirect_less {
	template <class P>
	bool operator()(const P& x, const P& y) const { return *x < *y; }
};

void test_9(int N)
{
	std::unique_ptr<int>* ia = new std::unique_ptr<int>[N];
	for (int i = 0; i < N; ++i)
		ia[i].reset(new int(i));
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N, indirect_less());
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(ia, ia + i, indirect_less()) == ia + i);
		CHECK(std::is_heap(ia, ia + i - 1, indirect_less()));
	}
	delete[] ia;
}

template <typename T>
struct construct {
	template <typename ...Us>
	T operator()(Us&& ... us) const
	{
		return T{((Us&&) us)...};
	}
};

struct S {
	int i;
};

void test_10(int N)
{
	int* ia = new int[N];
	S* ib = new S[N];
	for (int i = 0; i < N; ++i)
		ia[i] = i;
	std::shuffle(ia, ia + N, gen);
	std::make_heap(ia, ia + N);
	std::transform(ia, ia + N, ib, construct<S>());
	for (int i = N; i > 0; --i) {
		CHECK(stl2::pop_heap(ib, ib + i, std::less<int>(), &S::i) == ib + i);
		std::transform(ib, ib + i, ia, std::mem_fn(&S::i));
		CHECK(std::is_heap(ia, ia + i - 1));
	}
	CHECK(stl2::pop_heap(ib, ib, std::less<int>(), &S::i) == ib);
	delete[] ia;
	delete[] ib;
}

}

TEST_CASE("alg.pop_heap")
{
	test_1(1000);
	test_2(1000);
	test_3(1000);
	test_4(1000);
	test_5(1000);
	test_6(1000);
	test_7(1000);
	test_8(1000);
	test_9(1000);
	test_10(1000);
}
